﻿// 使用计数排序对输入数组进行排序
void CountSort(int[] arr)
{
    // 查找数组中的最大值和最小值
    int max = arr[0];
    int min = arr[0];

    // 遍历数组以找到最大和最小值
    for (int i = 0; i < arr.Length; i++)
    {
        // 更新最大值
        if (arr[i] > max)
        {
            max = arr[i];
        }

        // 更新最小值
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }

    // 创建计数数组，长度为最大值和最小值之差加1
    int[] count = new int[max - min + 1];

    // 遍历数组并在计数数组中对应位置增加计数
    for (int i = 0; i < arr.Length; i++)
    {
        count[arr[i] - min]++;
    }

    // 重新排列原始数组
    int index = 0;
    for (int i = 0; i < count.Length; i++)
    {
        // 根据计数数组中的计数，将元素回写到原始数组中
        while (count[i]-- > 0)
        {
            arr[index++] = i + min;
        }
    }
}
int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
CountSort(arr);
Console.WriteLine("Sorted array is:");
foreach (int i in arr)
{
    Console.Write(i + " ");
}